package BFS;

import java.util.*;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-03-09
 * Time:14:09
 * Text：130. 被围绕的区域
 */
public class Text4 {

    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    int m,n;
    boolean[][] bd=new boolean[201][201];
    public void bfs(char[][] board,int i,int j)
    {
        Queue<int[]> q = new LinkedList<>();
        if(board[i][j] != 'O') return;
        board[i][j]='.';
        q.add(new int[]{i,j});
        while(!q.isEmpty())
        {
            int[] arr=q.poll();
            for(int k = 0;k < 4; k++)
            {
                int x = arr[0] + dx[k] , y = arr[1] + dy[k];
                if(x >= 0 && x <= m-1 && y >= 0 && y <= n-1 && board[x][y] == 'O')
                {
                    q.add(new int[]{x,y});
                    board[x][y]='.';
                }
            }
        }

    }
    public void solve(char[][] board) {
        m = board.length; n = board[0].length;
        for(int i=0;i<n;i++){
            //负责第一行
            bfs(board,0,i);
            //下边
            bfs(board,m-1,i);

        }
        for(int i=0;i<m;i++)
        {
            bfs(board,i,n-1);  //右边
            bfs(board,i,0);   //左边
        }

        for(int i = 0 ;i < m ;i++)
        {
            for(int j = 0 ;j < n ;j++)
            {
                if(board[i][j] == 'O')
                    board[i][j]='X';
                if(board[i][j]=='.')
                    board[i][j]='O';
            }
        }

    }
    public static void main(String[] args) {
        Text4 t1=new Text4();
        char[][] array={{'X','O','X'},
                        {'O','X','O'},
                        {'X','O','X'}};
        t1.solve(array);
        System.out.println();
    }
}
